package LeetCode._01算法入门.day10递归回溯;

import org.junit.Test;
import utils.MyPrintUtil;

/**
 * @author 挚爱之夕
 * @date 2022-03-01 - 03 - 01 - 18:08
 * @Description 将两个升序链表合并为一个新的升序链表并返回。
 * 新链表是通过拼接给定的两个链表的所有节点组成的。
 * @Version 简单
 */
public class _21合并两个有序链表 {
    static ListNode list1;  // 1->2->4
    static ListNode list2;  // 1->3->4
    static {
        list1 = new ListNode(1);
        ListNode h1 = list1;
        h1.next = new ListNode(2);
        h1 = h1.next;
        h1.next = new ListNode(4);

        list2 = new ListNode(1);
        ListNode h2 = list2;
        h2.next = new ListNode(3);
        h2 = h2.next;
        h2.next = new ListNode(4);
    }
    //by me
    @Test
    public void solve(){
        ListNode res = mergeTwoLists(list1, list2);
        MyPrintUtil.printSingleLinkedList(res);//1->1->2->3->4->4
        System.out.println("\n-----------");
        MyPrintUtil.printSingleLinkedList(list1);
        System.out.println("\n-----------");
        MyPrintUtil.printSingleLinkedList(list2);
    }
    //递归
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;
        int val = Math.min(list1.val, list2.val);
        ListNode head = new ListNode(val);
        if(val == list1.val){
            head.next = mergeTwoLists(list1.next, list2);
        }else{
            head.next = mergeTwoLists(list1, list2.next);
        }
        return head;
    }
    //迭代
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2){
        //考虑空表的情况
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;
        //由两个链表的最小值创建新链表表头
        ListNode head;


        if(list1.val < list2.val){
            head = new ListNode(list1.val);
            list1 = list1.next;
        }else{
            head = new ListNode(list2.val);
            list2 = list2.next;
        }


        ListNode p = head;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = new ListNode(list1.val);
                p = p.next;
                list1 = list1.next;
            }else{
                p.next = new ListNode(list2.val);
                p = p.next;
                list2 = list2.next;
            }
        }

        if(list1 != null){
            p.next = list1;
        }else if(list2 != null){
            p.next = list2;
        }

        return head;
    }
}
